package Semantics;

import java.util.ArrayList;

class Bucket{
	String key;
	Object binding;
	Bucket next;
	
	Bucket(String k, Object b, Bucket n){
		key = k;
		binding = b;
		next = n;
	}
}

public class HashT {
	private final int SIZE = 1024;
	private final int BITSIZE = SIZE / 32;
	private Bucket table[] = new Bucket[SIZE];
	private int size = 0;
	private int[] used = new int[BITSIZE]; //used as a bitmap
	
	private int hash(String s){
		int h = 0;
		for(int i = 0; i < s.length(); ++i){
			h = (int) (h * 6.5599 + s.charAt(i));
		}
		return h;
	}
	
	public void insert(String s, Object b){
		int index = hash(s) % SIZE;
		table[index] = new Bucket(s,b,table[index]);
		size += 1;
		used[index / 32] |= (1 << index % 32);
	}
	
	public Object lookup(String s){
		int index = hash(s) % SIZE;
		for(Bucket b = table[index]; b != null; b = b.next){
			if(s.equals(b.key))
				return b.binding;
		}
		return null;
	}
	
	public Object[] lookupall(String s){
		int index = hash(s) % SIZE;
		for(Bucket b = table[index]; b != null; b = b.next){
			if(s.equals(b.key)){
				ArrayList<Object> ar = new ArrayList<Object>();
				while(b != null){
					ar.add(b.binding);
					b = b.next;
				}
				return ar.toArray();
			}
		}
		return null;
	}
	
	public void pop(String s){
		int index = hash(s) % SIZE;
		if(table[index] != null){
			table[index] = table[index].next;
			size -= 1;			
			if(table[index] == null){
				used[index / 32] &= ~(1 << index % 32);
			}
		}
	}
	
	public Object[] getall(){
		ArrayList<Object> res = new ArrayList<Object>();
		
		for(int i = 0; i < SIZE; ++i){
			Bucket bucket = table[i];
			while(bucket != null){
				res.add(bucket.binding);
				bucket = bucket.next; 
			}
		}
		return res.toArray();
	}
	
	public void clear(){
		size = 0;
		int index = 0;
		for(int i = 0; i < BITSIZE; ++i){
			int temp = used[i];
			while(temp > 0){
				if(temp % 2 > 0){
					table[index] = null;
				}
				temp /= 2;
				index += 1;
			}
		}
	}
}
